package com.my.algorithmlearning.leetcode;

import com.my.algorithmlearning.entity.ListNode;
import org.springframework.util.Assert;

/**
 * @ClassName Medium_142_DetectCycle
 * @Description 参考题解：https://leetcode.cn/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
 * @Author wanghaiwei
 * @Date 2023/4/26 17:29
 */
public class Medium_142_DetectCycle {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return null;
        }
        ListNode slowPointer = head;
        ListNode fastPointer = head;
        while (slowPointer != null && fastPointer != null) {
            slowPointer = slowPointer.next;
            if (fastPointer.next != null) {
                fastPointer = fastPointer.next.next;
            } else {
                fastPointer = null;
            }
            if (slowPointer == fastPointer) {
                break;
            }
        }
        if (slowPointer == null || fastPointer == null) {
            return null;
        }
        //让fast指针从头部重新走
        fastPointer = head;
        while (fastPointer != slowPointer) {
            fastPointer = fastPointer.next;
            slowPointer = slowPointer.next;
        }
        return slowPointer;
    }

    public static void main(String[] args) {
        Medium_142_DetectCycle solution = new Medium_142_DetectCycle();
        ListNode result = solution.detectCycle(ListNode.convertArrayToListNode(new int[]{3, 2, 0, -4}, 1));
        Assert.isTrue(result.val == 2, "Input: head = [3,2,0,-4], pos = 1，计算错误，预期2，实际：" + result.val);

        result = solution.detectCycle(ListNode.convertArrayToListNode(new int[]{1, 2}, 0));
        Assert.isTrue(result.val == 1, "Input: head = [1,2], pos = 0，计算错误，预期1，实际：" + result.val);

        result = solution.detectCycle(ListNode.convertArrayToListNode(new int[]{1}));
        Assert.isTrue(result == null, "Input: head = [1], pos = -1，计算错误，预期null");

        result = solution.detectCycle(ListNode.convertArrayToListNode(new int[]{-1, -7, 7, -4, 19, 6, -9, -5, -2, -5}, 6));
        Assert.isTrue(result.val == -9, "Input: head = [-1,-7,7,-4,19,6,-9,-5,-2,-5], pos = 6，计算错误，预期-9， 实际:" + result.val);
    }
}
